package com.Algorithm.DynamicProgramming.三角形问题;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2022/04/12/10:33
 * @Description:
 * @Target:
 */
public class 数字三角形问题_数塔问题 {
    /*
    *
    * 数字三角形问题（数塔问题）
        Description
        下图给出了一个数字三角形，请编写一个程序，计算从顶至底的某处的一条路径，使该路径所经过的数字和最大,从顶部向下走，每次只能走下面或者右下
        Input
        有很多个测试案例，对于每一个测试案例， 通过键盘逐行输入，第1行是输入整数（如果该整数是0,就表示结束，不需要再处理），
        表示三角形行数n，然后是n行数
        Output
        输出最大值
        Example Input

        5
        7
        3 8
        8 1 0
        2 7 4 4
        4 5 2 6 5

        Example Output

        30

    *
    * */

    // 子问题的联系:1.下面和右下.---下面大的不一定打,右下同理,所以需要遍历.


    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = in.readLine().charAt(0) - '0';
        int[][] ints = new int[n][n];

        for (int i = 0; i < n; i++) {
            String[] s = in.readLine().split(" ");
            for (int j = 0; j <= i; j++) {
                ints[i][j] = Integer.valueOf(s[j]);
            }
        }


        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(ints[i][j]+" ");
            }
            System.out.println();
        }

        System.out.println("---------");
        System.out.println(dp(ints, 0, 0));
    }

    // 入参数组，坐标
    static int dp(int[][] ints,int x,int y){
        if (y>x || x>=ints.length || y>=ints[0].length){
            return 0;
        }

        if (x==ints.length-1){
            return ints[x][y];
        }else {
            return  Math.max(dp(ints,x+1,y),dp(ints,x+1,y+1))+ints[x][y];
        }

    }
}
